package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import two.chapter_1.c1_1.Printer;

public class Ex1_4_20 {

    /**
     * 3LogN
     * @param args
     */
    public static void main(String[] args) {
        //双调数组
        int[] a = generateBitonicArray(30);
        Printer.printArray(a);
        //查找最大值   logN
        StdOut.println("max:"+a[findMaxInBitonicArray(0, a.length - 1, a)]);


        //0~maxIndex  递增  二分查找   logN

        //maxIndex+1~ a.lenght-1   递减  二分查找 logN
    }

    private static int[] generateBitonicArray(int N) {
        int a[] = new int[N];
        int mid = N / 2;

        a[0] = StdRandom.uniform(5);
        for (int i = 1; i <= mid; i++) {
            a[i] = a[i - 1] + StdRandom.uniform(5) + 5;
        }

        for (int i = mid + 1; i < N; i++) {
            a[i] = a[i - 1] - 1-StdRandom.uniform(5);
        }
        return a;
    }

    private static int findMaxInBitonicArray(int lo, int hi, int[] a) {
        if (lo == hi) {
            return lo;
        }
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[mid + 1]) {
            return findMaxInBitonicArray(lo, mid, a);
        } else if (a[mid] < a[mid + 1]) {
            return findMaxInBitonicArray(mid + 1, hi, a);
        }else {
            return mid;
        }


    }
}
